Contracting out data storage functions to storage service providers that operate external servers (e.g., “the cloud”) is a major industry trend that offers great benefits to database owners. At the same time, the contracting out of data storage functions raises confidentiality and privacy concerns. Simple encryption of such data is a hindrance to search capabilities such as the data owner wanting to search a backup or email archive, or query a database via attribute-value pairs. This problem has motivated much research on advanced searchable encryption schemes that enable searching on the encrypted data while attempting to protect the confidentiality of data and queries.